class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        res= []
        for i in range(5):
            if i > num:
                break
            res1 = []
            self.hour_dfs(i, 3, 0, res1)
            res2 = []
            self.minute_dfs(num - i, 5, 0, res2)
            for k in res1:
                for r in res2:
                    res.append('{}:{}'.format(k,r))
        return res
        
    def hour_dfs(self, count, cur_index, out, res):
        # count 剩余led灯的数量
        # cur_index 当前遍历到的灯的索引 3 2 1 0
        if count == cur_index + 1:
            temp = (1 << (cur_index + 1)) - 1 + out
            if temp >= 12:
                return
            res.append(temp)
            return
        elif count > cur_index + 1:
            return
        elif count == 0:
            if out >= 12:
                return
            res.append(out)
            return
        else:
            self.hour_dfs(count, cur_index - 1, out, res)
            self.hour_dfs(count - 1, cur_index - 1, out + (1 << cur_index), res)
        
    def minute_dfs(self, count, cur_index, out, res):
        # count 剩余led灯的数量
        # cur_index 当前遍历到的灯的索引 3 2 1 0
        if count == cur_index + 1:
            temp = (1 << (cur_index + 1)) - 1 + out
            if temp >= 60:
                return
            if temp < 10:
                temp = '0' + str(temp)
            res.append(temp)
            return
        elif count > cur_index + 1:
            return
        elif count == 0:
            if out >= 60:
                return
            if out < 10:
                out = '0' + str(out)
            res.append(out)
            return
        else:
            self.minute_dfs(count, cur_index - 1, out, res)
            self.minute_dfs(count - 1, cur_index - 1, out + (1 << cur_index), res)